// 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
// 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
// 思路，回溯
// 此题关键在于分割字符串的同时要加上分割点，注意起始位置startIndex 为i + 2
// 终止条件为当点数等于3的时候只需要判断后面的子串是否合法即可
function restoreIpAddresses(s) {
    let result = []
    function isValid(s, start, end) {
        if (start > end) {
            return false
        }
        if (s[start] === '0' && start !== end) {
            return false
        }
        let num = 0
        for (let i = start; i <= end; i++) {
            if (s[i] > 9 || s[i] < 0) {
                return false
            }
            num = num * 10 + Number(s[i])
            if (num > 255) {
                return false
            }            
        }
        return true
    }
    function backtracking(s, startIndex, pointNum) {
        if (pointNum === 3) {
            if (isValid(s, startIndex, s.length - 1)) {
                result.push(s)
            }
            return
        }
        for (let i = startIndex; i < s.length; i++) {
            if (isValid(s, startIndex, i)) {
                backtracking(s.substring(0, i + 1) + '.' + s.substring(i + 1), i + 2, pointNum + 1)
            } else {
                // 直接break，后面的循环没必要了
                break
            }            
        }
    }
    if (s.length > 12) {
        return []
    }
    backtracking(s, 0, 0)
    return result
}

let s = "25525511135"
console.log(restoreIpAddresses(s))